import java.util.Stack;

/**
 * @program: LeetCode
 * @description: LeetCode : 剑指 Offer II 037. 小行星碰撞
 * @author: WXY
 * @create: 2022-12-27 17:03
 * @Version 1.0
 **/

public class Num_offer2_037_asteroidCollision {
    public static int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        int len = asteroids.length;
        for (int i = 0; i < len; i++) {
            if (stack.isEmpty() || asteroids[i] > 0) {
                stack.push(asteroids[i]);
                continue;
            }
            //此时asteroids[i] 是一个负值
            int cur = -asteroids[i];
            while (!stack.isEmpty() && cur > Math.abs(stack.peek()) && stack.peek() > 0) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                if (stack.peek() == cur) {
                    stack.pop();
                } else if (stack.peek() < 0) {
                    stack.add(asteroids[i]);
                }

            }else {
                stack.add(asteroids[i]);
            }
        }
        int size = stack.size();
        int[] ans = new int[size];
        for (int i = 0; i < size; i++) {
            ans[i] = stack.pop();
        }
        int left = 0;
        int right = ans.length - 1;
        while (left < right) {
            swap(ans, left++, right--);
        }
        return ans;
    }

    private static void swap(int[] ans, int l, int r) {
        int tep  = ans[l];
        ans[l] = ans[r];
        ans[r] = tep;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{-2,-2,-1,-2,5,-10};
        int[] ints = asteroidCollision(arr);
        for (int n : ints) {
            System.out.print(n + " ");

        }
    }
}
